package com.flower.algorithm.linklist;

import java.util.Objects;

/**
 * @ClassName JosephuNode
 * @Description 约瑟夫环问题，双向链表
 * @Author 吃麻椒的花酱
 * @Date 2021/11/20 23:15
 * @Version 1.0
 */
public class JosephuNode {
    public int val;
    public JosephuNode next;
    public JosephuNode() {};
    public JosephuNode(int val) { this.val = val; }
    public JosephuNode(int val, JosephuNode next) { this.val = val; this.next = next; }

    public static JosephuNode creatJosephuNode(int number){
        if (number < 0) {
            throw new IllegalArgumentException("number不能小于0");
        }
        JosephuNode fristNode=null;
        JosephuNode tempNode=null;
        for (int i = 1; i <= number; i++) {
            // 特殊判断第一个节点 相当于创建头结点
            if (fristNode == null) {
                fristNode=new JosephuNode(i);
                fristNode.next=fristNode;
                tempNode = fristNode;
            }else {
                JosephuNode newNode=new JosephuNode(i);
                tempNode.next=newNode;
                newNode.next = fristNode;
                tempNode=tempNode.next;

            }
        }
        return fristNode;
    }

    public static void shouJosephuNode(JosephuNode node){
        if (node == null) {
            return;
        }
        JosephuNode temp=node;
        do {
            System.out.println(temp.val);
            temp=temp.next;
        }while (temp !=node);
       /* while(true){

            if(temp.next==node)
                break;
            temp=temp.next;
        }*/
    }

    public static void lastJosephuNode(JosephuNode node,int startNode,int countNode){
        if(node==null)
        {
            return;
        }
        JosephuNode temp = node;
        while (true) {
            if(temp.next == node)
                break;
            temp = temp.next;
        }
        // 为什么是startNode-1  常规来说游戏时 是从当前起点开始计算第一个人 所以循环需要少走一次
        for (int i = 0; i < startNode-1; i++) {
            node=node.next;
            temp = temp.next;
        }
        while (true) {
            if (temp.next == node) {
                break;
            }
            for (int i = 0; i < countNode-1; i++) {
                temp = temp.next;
                node = node.next;
            }
            node=node.next;
            // temp始终指向node前一个
            temp.next=node;
        }
        System.out.println(temp.val);
    }


    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (o == null || getClass() != o.getClass()) return false;
        JosephuNode that = (JosephuNode) o;
        return val == that.val && Objects.equals(next, that.next);
    }

    @Override
    public int hashCode() {
        return Objects.hash(val, next);
    }
}
